package com.code.leetcode._202507;

/**
 * 41. 缺失的第一个正数
 ***/
public class FirstMissingPositive {

    /**
     * 给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数
     * 请你实现时间复杂度为O(n)并且只能使用常熟级别的额外空间的解决方案
     * 示例1：输入：nums=[1,2,0]
     * 输出：3
     * 解释：范围[1,2]中的数字都在数组中
     * 示例2：输入：nums=[3,4,-1,1]
     * 输出：2
     * 解释：1在数组中，但2没有
     * 示例3：输入：nums=[7,8,9,11,12]
     * 输出：1
     * 解释：最小的正数1没有出现
     */

    public static void main(String[] args) {
        FirstMissingPositive f = new FirstMissingPositive();
        System.out.println(f.firstMissingPositive1(new int[]{3, 4, -1, 1, 9, -5}));
    }

    /**
     * 如果本题没有额外的时空复杂第要求，那么很容易实现
     * 1、我们可以将数组所有的数放入哈希表，随后从1开始依次枚举正整数，并判断其是否在哈希表中；
     * 2、我们可以从1开始依次枚举正整数，并遍历数组，判断其是否在数组中
     * 如果数组的长度为N，那么第一种做法的时间复杂度为O(N),空间复杂度为O(N)；第二种做法的时间复杂度为O(N^2),空间复杂度为O(1).
     * 但他们都不满足时间复杂度O(N)且空间复杂度为O(1)。
     * 真正 满足时间复杂度为O(N)且时间复杂度为O(1)的算法是不存在的，但是我们可以退而求其次；利用给定数组中的时间来存储一些状态。也就是说，
     * 如果题目给定的数组是不可修改的，那么就不存在满足时空复杂度要求的算法，但如果我们可以修改给定的数组，那么是存在满足要求的算法的
     * <p>
     * 方案一：哈希表
     * 我们可以将数组所有的数放入哈希表，随后从1开始依次枚举正整数，并判断其是否在哈希表中；
     * 仔细想一想，我们为什么要使用哈希表？这是因为哈希表是一种可以支持快速查询的数据结构:给定一个元素，我们可以在O(1)的时间查找该元素是否
     * 在哈希表中。因此我们可以考虑将给定的数组设计成哈希表的  替代产品
     * 实际上，对于一个长度为N的数组，其中没有出现的最小正整数只能是[1,N+1]中。这是因为如果[1,N]都出现了，那么答案是N+1，否则答案是[1,N]
     * 中没有出现的最小正整数。这样以来，我们将所有[1,N]范围内的数放入哈希表，也可以得到最终的答案，而给定的数组恰好长度为N,这让我们有了一个
     * 将数组设计成哈希表的思路。
     * 我们将数组进行遍历，对于遍历到的数x，如果它在[1,N]的范围内，那么就将数组中的第X-1个位置(注意：数组下标从0开始)打上 标记
     * 在遍历结束之后，如果所有的位置都被打上了标记，那么答案是N+1，否则答案是最小的没有打上标记的位置加1
     * 那么我们如何设计这个 标记 呢？由于数组的数没用任何限制，因此这并不是一件容易的事情。但我们可以继续利用上面的提到的性质：由于我们只
     * 在意[1,N]中的数，因此我们可以先对数组进行遍历，把不在[1,N]范围内的数修改成任意一个大于N的数 例如N+1 .这样一来，数组中的所有数都是正数了
     * 因此我们可以将 标记 表示为 负号 。算法的流程如下：
     * 1、我们将数组中的所有小于等于0的数修改为N+1
     * 2、我们遍历数值中的每一个数x。它可能已经被打上了标记。因此对于原本对应的数为|x|，其中||为绝对值符号。如果|x|属于|1,N|，那么我们给数组
     * 中的第|x|-1个位置的数添加一个符号。注意如果它已经有负号了，不需要重复添加。
     * 3、在遍历完成之后，如果数组中的每一个数都是负数，那么答案是N+1，否则答案是第一个整数的位置加1
     **/
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
        //相当于将数组进行了一次排序
        for (int i = 0; i < n; i++) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
    }

    /**
     * 置换
     * 除了打标记以外，我们还可以使用置换的方法，将给定的数组 恢复 成下面的形式：
     * 如果素组中包含x属于[1,N]，那么恢复后，数组的第x-1个元素为x
     * 在恢复后，数组应当有[1,2,...,N]的形式，但其中有若干个位置上的数是错误的，每一个错误的位置就代表了一个缺失的正数。以题目的示例二[3,4,-1,1]
     * 为例，恢复后的数组应当为[1,-1,3,4],我们就可以知道缺失的数为2.
     * 那么我们如何将数组进行恢复呢？我们可以对数组进行一次遍历，对于遍历到的数x=nums[i]，如果x属于[1,N]，我们将知道x应当出现在数组中的x-1的位置，
     * 因此交换nums[i]和nums[x-1]，这样x就出现了正确的位置。在完成交换后，新的nums[i]可以拿还在[1,N]的范围内，我们需要继续进行交换操作，知道x不属于[1,N]。
     * 注意到上面的方法可能陷入死循环。如果nums[i]恰好于nums[x-1]相等，那么就会无线交换下去。此时我们有nums[i]=x=nums[x−1]，说明x已经出现了正确的
     * 位置。因为我们可以跳出循环，开始遍历下一个数。
     * 由于每次的交换操作都会使得某一个数交换到正确的位置，因此交换的次数最多为N，整个方法的时间复杂度为O(N)
     **/
    public int firstMissingPositive1(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }

}
